#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "algorithm.h"
/**
 * @brief  算法接口
 * @param  input            输入参数
 * @param  output           输出参数
 * @return int32_t          返回成功或者失败，RETURN_OK 或 RETURN_ERROR
 */
 /*快排函数*/
void sort_eboc(IOUint * a,int32_t l,int32_t r){
    srand(time(NULL));
    int32_t  mid=l+rand()%(r-l+1);
    int32_t  i=l,j=r;
    IOUint t=a[mid];
    a[mid]=a[i];
    a[i]=t;
    while(i<j){
        while (a[j].startLpos>t.startLpos && j>i) j--;
        if (i<j) {a[i]=a[j];i++;}  
        while (a[i].startLpos<t.startLpos && j>i) i++;
        if (i<j) {a[j]=a[i];j--;}  
    }
    a[i]=t;
    if (l<j-1) sort_eboc(a,l,j-1);
    if (r>i+1) sort_eboc(a,i+1,r);
}
/*计算队列贡献*/
int32_t queue_cost(int32_t x,int32_t l,ID* D,IOVector *a){
    int32_t cost=0;
    HeadInfo start,end;
    if (x>0) {
        start.wrap=a[D[x-1].b].ioArray[D[x-1].daid].wrap;
        start.lpos=a[D[x-1].b].ioArray[D[x-1].daid].endLpos;
        start.status=HEAD_RW;
        end.wrap=a[D[x].b].ioArray[D[x].daid].wrap;
        end.lpos=a[D[x].b].ioArray[D[x].daid].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x+1<l) {
        start.wrap=a[D[x].b].ioArray[D[x].daid].wrap;
        start.lpos=a[D[x].b].ioArray[D[x].daid].endLpos;
        start.status=HEAD_RW;
        end.wrap=a[D[x+1].b].ioArray[D[x+1].daid].wrap;
        end.lpos=a[D[x+1].b].ioArray[D[x+1].daid].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    return cost;
}
//能量不足的时候不要开启一个具有挑战性的对话
//理论意识是一种“类”意识
//从论域到论题——题目不要太大
//时空限定、类型分割、方法选择
void repub(int32_t x,int32_t y,OutputParam *output, OutputParam *newo){//将原x位置的IO移到y位置
    int32_t l=output->len;
    if (x==y) return;
    if (x<y) {
        for(int32_t i=0;i<x;i++) newo->sequence[i]=output->sequence[i];
        for(int32_t i=x;i<y;i++) newo->sequence[i]=output->sequence[i+1];
        newo->sequence[y]=output->sequence[x];
        for(int32_t i=y+1;i<l;i++) newo->sequence[i]=output->sequence[i];
    }
    else{
        for(int32_t i=0;i<y;i++) newo->sequence[i]=output->sequence[i];
        newo->sequence[y]=output->sequence[x];
        for(int32_t i=y;i<x;i++) newo->sequence[i+1]=output->sequence[i];
        for(int32_t i=x+1;i<l;i++) newo->sequence[i]=output->sequence[i];
    }
}
/*交换序列对应位置*/ 
void swap(int32_t x,int32_t y,ID* D,int32_t *a ){
    ID z;
    int32_t p;
    z=D[x];D[x]=D[y];D[y]=z;
    p=a[x];a[x]=a[y];a[y]=p;
}
/*指数函数*/
double expe(double x)
{
    int32_t T=8;
    x = 1.0 + x/256;
    while(T--) x *= x;
    return x;
}
/*调试函数*/
void print_eboc(IOVector eb){
    printf("wrap kind %d sort :\n",eb.ioArray[0].wrap%2);
    for(int32_t i=0;i<eb.len;i++){
        printf("\t%u\n",eb.ioArray[i].startLpos);
    }
}
void print_SeekTimeCalculate(const InputParam *input){
    HeadInfo start = {input->ioVec.ioArray[0].wrap, input->ioVec.ioArray[0].endLpos, HEAD_RW};
    HeadInfo end = {input->ioVec.ioArray[1].wrap, input->ioVec.ioArray[1].endLpos, HEAD_RW};
    int32_t seekT = 0;
    int32_t beltW = 0;
    int32_t motorW = 0;
    printf("\nSeekTimeCalculate:%u\n",input->ioVec.len);
       for (uint32_t i = 0; i < (input->ioVec.len)-1; i++) {
           start.wrap=input->ioVec.ioArray[i].wrap;
           start.lpos=input->ioVec.ioArray[i].endLpos;
           start.status= HEAD_RW;
           end.wrap=input->ioVec.ioArray[i+1].wrap;
           end.lpos=input->ioVec.ioArray[i+1].startLpos ;
           end.status=HEAD_RW;
           seekT = SeekTimeCalculate(&start, &end);
           beltW = BeltWearTimes(&start, &end, NULL);
           motorW = MotorWearTimes(&start, &end);
           printf("\t%d(ms)\n",seekT);
       }
}
int32_t max(int32_t a,int32_t b){
    return a>b?a:b;
}
int32_t min(int32_t a,int32_t b){
    return a<b?a:b;
}
/************/

int32_t IOScheduleAlgorithm(const InputParam *input, OutputParam *output)
{
    int32_t ret,signal;
    HeadInfo thead={input->headInfo.wrap,input->headInfo.lpos,input->headInfo.status };
    /* 算法：scan */
    output->len = input->ioVec.len;
    /*sort part*/
    ID* D=(ID*)malloc(output->len*sizeof(ID));
    IOVector eboc[2];
    eboc[0].ioArray= (IOUint *)malloc(output->len * sizeof(IOUint));
    eboc[0].len=0;
    eboc[1].ioArray= (IOUint *)malloc(output->len * sizeof(IOUint));
    eboc[1].len=0;
    for (uint32_t i = 0; i < output->len; i++) {
        signal=input->ioVec.ioArray[i].wrap%2;
        eboc[signal].ioArray[eboc[signal].len]=input->ioVec.ioArray[i];
        eboc[signal].len++;
    }
    sort_eboc(eboc[0].ioArray,0,eboc[0].len-1);
    sort_eboc(eboc[1].ioArray,0,eboc[1].len-1);
    //print_eboc(eboc[0]);print_eboc(eboc[1]);
    dnode hd[2],p,q;
    hd[0]=(dnode)malloc(sizeof(dNode));hd[1]=(dnode)malloc(sizeof(dNode));
    hd[0]->next=NULL;
    p=hd[0];
    for(int32_t i=0;i<eboc[0].len;i++){
        q=(dnode)malloc(sizeof(dNode));
        q->data=i;q->next=NULL;
        p->next=q;p=q;
    }
    p=hd[1];
    p->next=NULL;
    for(int32_t i=0;i<eboc[1].len;i++){
        q=(dnode)malloc(sizeof(dNode));
        q->data=i;q->next=p->next;
        p->next=q;
    }
    int32_t l=0;
    while (l<input->ioVec.len) {  
        p=hd[0];q=hd[0]->next; 
        while(q){
            while(q &&
            eboc[0].ioArray[q->data].startLpos<=thead.lpos) {
                p=q;
                q=q->next;
            }
            if (q){
                output->sequence[l]=eboc[0].ioArray[q->data].id;
                D[l].b=0;D[l].daid=q->data;
                l++;
                thead.lpos=eboc[0].ioArray[q->data].endLpos;
                p->next=q->next;
                free(q);
                q=p->next;
            }
        }  
        thead.lpos=MAX_LPOS;
        p=hd[1];q=hd[1]->next; 
        while(q){
            while(q &&
            eboc[1].ioArray[q->data].startLpos>=thead.lpos) {
                p=q;
                q=q->next;
            }
            if (q){
                output->sequence[l]=eboc[1].ioArray[q->data].id;
                D[l].b=1;D[l].daid=q->data;
                l++;
                thead.lpos=eboc[1].ioArray[q->data].endLpos;
                p->next=q->next;
                free(q);
                q=p->next;
            }
        }
        thead.lpos=0;
    }
    /*基于scan开始模拟退火过程*/
    double T=100000,endT=0.1;
    double d=0.98;
    int32_t *rep=malloc(l*sizeof(int32_t));
    ID *D1=(ID*)malloc(l*sizeof(ID));
    while(T>endT){
        srand(T*100000);
        for(int32_t i=0;i<l;i++){
            rep[i]=output->sequence[i];
        }
        int32_t x[6];
        int32_t cost1=0,cost2=0;
        for(int32_t i=0;i<6;i++){
            int32_t flag=0;
            do{
                flag=0;
                x[i]=rand()%l;
                for(int32_t j=0;j<i;j++){
                    if (x[i]==x[j]) {
                        flag=1;
                        break;
                    }
                }
            }while(flag);
        }
/*      for(int32_t i=0;i<6;i++){
            printf("%d ",x[i]);
        }
        printf("\n");*/ 
        int32_t costi,costy;  
        AccessTime aci={0},acy={0};     
        TotalAccessTime(input,output,&aci);
        costi=aci.addressDuration;
        for(int32_t j=0;j<6;j++){     
            int32_t y=x[j];  
            OutputParam *o1=(OutputParam*)malloc(sizeof(OutputParam));
            o1->sequence=(uint32_t*)malloc(l*sizeof(uint32_t));
            o1->len=l;
            for(int32_t i=max(0,x[j]-10);i<min(l,x[j]+10);i++){
                if (i!=x[j]) {
                    acy.addressDuration=0;
                    acy.readDuration=0;
                    repub(x[j],i,output,o1);
                    TotalAccessTime(input,o1,&acy);
                    costy=acy.addressDuration;
                    if (costy<costi) {
                        costi=costy;
                        uint32_t *t=output->sequence;
                        output->sequence=o1->sequence;
                        o1->sequence=t;
                        /*for(int32_t k=0;k<l;k++){
                            printf("%d ",output->sequence[k]);
                        }*/
                        printf("%d\n",costi);
                    }
                }
            }
            costi;
            free(o1->sequence);
            free(o1);
        }
        cost2=costi;
        if (cost2>=cost1){
            srand(time(NULL));
            double p=expe(((double)(cost2-cost1))/T);
            int32_t zp=(int32_t)p*10000000;
            int32_t ra=rand()%10000000;
            if (ra>=zp) {
                for(int32_t i=0;i<l;i++){
                    output->sequence[i]=rep[i];
                }
            } 
        }
        T=T*d;
    }
    /* 调用公共函数示例：调用电机寻址、带体磨损、电机磨损函数 */
    free(D);
    free(D1);
    free(rep);

    /* 调用公共函数示例：调用IO读写时间函数 */
    uint32_t rwT = ReadTimeCalculate(abs(input->ioVec.ioArray[0].endLpos - input->ioVec.ioArray[0].startLpos));
    free(eboc[0].ioArray);
    free(eboc[1].ioArray);
    free(hd[0]);free(hd[1]);
    return RETURN_OK;
}

/**
 * @brief  算法运行的主入口
 * @param  input            输入参数
 * @param  output           输出参数
 * @return uint32_t          返回成功或者失败，RETURN_OK 或 RETURN_ERROR
 */
int32_t AlgorithmRun(const InputParam *input, OutputParam *output)
{
    int32_t ret;

    ret = IOScheduleAlgorithm(input, output);

    return RETURN_OK;
}
